#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time     : 2024/8/11 13:49
# @Author   : MingTai
# @File     : quick_sort.py
from typing import List


def quick_sort(lists: List[int]):
    if len(lists) <= 1:
        return lists
    else:
        mid_pivot = lists[0]
        less_before_mid_pivot = [i for i in lists[1:] if i <= mid_pivot]
        bigger_after_pivot = [i for i in lists[1:] if i > mid_pivot]
        finally_list = quick_sort(less_before_mid_pivot) + [mid_pivot] + quick_sort(bigger_after_pivot)
        return finally_list


def quick_pivot_2(list_arr):
    if len(list_arr) <= 1:
        return list_arr
    # 第零个元素作为中间值
    mid = list_arr[0]
    left_pivot = [i for i in list_arr[1:] if i < mid]
    right_pivot = [i for i in list_arr[1:] if i > mid]
    result = quick_pivot_2(left_pivot) + [mid] + quick_pivot_2(right_pivot)
    return result


# 冒泡排序，时间复杂度为O(n^2)
def bubble_sort(lists: List[int]):
    for i in range(len(lists)):
        for j in range(len(lists) - i - 1):
            if lists[j] > lists[j + 1]:
                lists[j], lists[j + 1] = lists[j + 1], lists[j]
                # lists[j], lists[j + 1] = lists[j], lists[j + 1]
    return lists


if __name__ == '__main__':
    aa = [2, 9, 5, 2, 4, 2, 1, 3, 9, 7]
    aaa = quick_sort([2, 9, 5, 2, 4, 2, 1, 3, 9, 7])
    # print(aaa)
    # print(bubble_sort(aaa))

    print(quick_pivot_2(aa))
